// 题目描述
// 讨论 (5.5K)
// 5. 最长回文子串
// 提示
// 中等
// 6.7K
// 给你一个字符串 s，找到 s 中最长的回文子串。
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
//   示例 1：
// 输入：s = "babad"
// 输出："bab"
// 解释："aba" 同样是符合题意的答案。
// 示例 2：
// 输入：s = "cbbd"
// 输出："bb"
//   提示：
// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成
// 通过次数
// 1.5M
// 提交次数
// 3.9M
// 通过率
// 37.7%
// https://leetcode.cn/problems/longest-palindromic-substring/

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let res = ''
  for (let i = 0; i < s.length; i++) {
    let s1 = palindrome(s, i, i)
    let s2 = palindrome(s, i, i + 1)
    res = res.length > s1.length ? res : s1
    res = res.length > s2.length ? res : s2
  }

  return res
}

/**
 * 寻找最长回文
 * 中心向两端扩散的双指针技巧
 * @param s
 * @param l
 * @param r
 * @returns {*}
 */
function palindrome(s, l, r) {
  // 注意防止下标越界
  while (l >= 0 && r < s.length && s[l] === s[r]) {
    --l
    ++r
  }

  // 由于 --l ++r 多执行了一次
  // 所以截取的时候要取 [l + 1, r - 1]
  return s.slice(l + 1, r)
}

console.log(
  longestPalindrome('babad'), // bab
  longestPalindrome('xxgengengngngnxx') // ngngngn
)













